#include <iostream>
using namespace std;


/* 将以k为根的子树调整为大根堆 */
template <typename T>                   //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void HeadAdjust(T A[], int k, int len)
{
    T tmproot = A[k];                     // 暂存子树的根节点
    for (int i = 2 * k; i <= len; i *= 2) // 沿key较大的子结点向下筛选
    { 
        if (i < len && A[i] < A[i + 1])
        {
            i++;                        // 取key较大的子结点的下标
        }
        if (tmproot >= A[i])
            break;                      // 筛选结束
        else
        {
            A[k] = A[i];                // 将A[i]调整到双亲结点上
            k = i;                      // 修改k值，以便继续向下筛选
        }
    }
    A[k] = tmproot;                        // 被筛选结点的值放入最终位置
}


/* 建立大根堆 */
template <typename T>                   //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void BuildMaxHeap(T A[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)   // 从后往前调整所有非终端节点
    { 
        HeadAdjust(A, i, len);
    }
}


/* 堆排序完整逻辑 */
template <typename T>                   //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void HeapSort(T A[], int len)
{
    BuildMaxHeap(A, len);               // 初始建栈
    for (int i = len-1; i > 1; --i)       //n-1趟的交换和建堆过程
    {
        swap(A[i], A[0]);               // 栈顶和栈底元素交换
        HeadAdjust(A, 1, i-1);          // 剩余的待排序元素整理成堆
    }
}

int main()
{
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
    int len = (int)sizeof(arr) / sizeof(*arr);
    HeapSort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;

    // float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4};
    // len = (int)sizeof(arrf) / sizeof(*arrf);
    // HeapSort(arrf, len);
    // for (int i = 0; i < len; i++)
    //     cout << arrf[i] << ' ' << endl;
    return 0;
}
